<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>斐波那契数列</title>
</head>
<body>
	<script>
	/*
	从第 3 项开始，当前项等于前两项之和： 1 1 2 3 5 8 13 21……

	使用动态规划，将复杂的问题拆分，也就是：F(N) = F(N - 1) + F(N - 2)，然后用数组将已经计算过的值存起来
	 */
	function fib(n) {
	  // 使用dp数组，将之前计算的结果存起来，防止栈溢出
	  let dp = [];
	  dp[0] = 1n; //  bigint  可以用来表示超过2^53-1的大整数
	  dp[1] = 1n;
	  for (let i = 2; i <= n; i++) {
	    dp[i] = dp[i - 1] + dp[i - 2]; // 注意： arr[i]
	  }
	  return dp[n];
	}
	console.log(fib(4)); // 1 1 2 3 5 => 5n
	</script>
</body>
</html>